package dp;

/**
 * 题意：给出n个点的空间坐标（n为偶数， n<=20）， 把他们配成n/2对， 问：怎样配对才能使点对的距离和最小？
 * <p>
 * 题解：
 * <p>
 * 设dp[s]为：状态为s（s代表着某个子集）时， 它的最小距离和。
 * <p>
 * 1.对于一个状态s， 首先要计算它减少两个点后的状态的最小距离和， 然后当前状态才能从这些状态中转移过来。
 * <p>
 * 2.如何转移：对于状态s， 在集合中随便找一个点，枚举集合中的其他点与它配对， 取距离和最小的那一对。
 * <p>
 * 3.为什么选定一个点，然后枚举集合中的其他点就可以呢？而两个点都要枚举呢？ 因为：对于选定的点， 它总得要和集合中的其他点配对， 那么答案就肯定蕴藏在某一次配对中了。而枚举两个点， 实际上是多余的。
 *
 * @author pengjz <br>
 * @version 1.0 <br>
 * @description OptimalPair <br>
 * @date 2021/10/20 11:21 <br>
 */
public class OptimalPair {

    public static final int INF = Integer.MAX_VALUE;
    public static final int MAX = 21;

    /**
     * 一个点
     */
    static class Node {
        double x, y, z;
    }

    private static int n;
    private static double[] dp = new double[1 << (MAX + 1)];

    /**
     * 求距离
     *
     * @param a 一个点
     * @param b 另一个点
     * @return 距离
     */
    private static double dis(Node a, Node b) {
        return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));
    }

    private static void solve() {
        dp[0] = 0;
        for (int i = 0; i < (1 << n); i++) {
            dp[i] = INF;
        }
        for (int i = 0; i < (1 << n); i++) {
            int f;
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    break;
                }
            }

            for (int j = 0; j < n; j++) {

            }
        }
    }
}
